﻿namespace Zipper.Applications

module BinaryTree =

    open Zipper.Zipper

    /// Binary tree.
    type tree<'l,'n> =
        | Leaf of 'l
        | Node of 'n * tree<'l,'n> * tree<'l,'n>

    let private moveLeft t =
        match t with
            | Leaf _ -> None
            | Node (x,l,r) ->
                let c = { new breadcrumb<_> with member y.Reconstruct(l') = Node (x,l',r) }
                Some (l,c)

    let private moveRight t =
        match t with
            | Leaf _ -> None
            | Node (x,l,r) ->
                let c = { new breadcrumb<_> with member y.Reconstruct(r') = Node (x,l,r') }
                Some (r,c)

    /// Tries to move to the left child.
    let tryLeft t = tryDown moveLeft t

    /// Moves to the left child.
    let left t = down moveLeft t

    /// Tries to move to the right child.
    let tryRight t = tryDown moveRight t

    /// Moves to the right child.
    let right t = down moveRight t